#include<bits/stdc++.h>
#define ll long long
#define mxn 1000003
#define md 1000000007
#define pb push_back
#define mkp make_pair
#define pq priority_queue
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
#define umap unordered_map
using namespace std;
inline int read(){
    int x=0;bool fl=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')fl=1;c=getchar();}
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return fl?-x:x;
}
int T,n,a[mxn];
ll t[mxn<<2],ad[mxn<<2];
void tag(int p,ll x){
    ad[p]+=x,t[p]+=x;
}
void push_down(int p){
    if(ad[p]){
        tag(p<<1,ad[p]),tag(p<<1|1,ad[p]);
        ad[p]=0;
    }
}
void build(int p,int l,int r){
    t[p]=-1e18,ad[p]=0;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
void change(int p,int x,ll y,int l,int r){
    if(l==r){
        t[p]=max(t[p],y);
        return;
    }
    push_down(p);
    int mid=(l+r)>>1;
    if(x<=mid)change(p<<1,x,y,l,mid);
    else change(p<<1|1,x,y,mid+1,r);
    t[p]=max(t[p<<1],t[p<<1|1]);
}
ll ask(int p,int l,int r,int L,int R){
    if(l>r)return -1e18;
    if(l<=L&&R<=r)return t[p];
    push_down(p);
    int mid=(L+R)>>1;
    if(l<=mid&&r>mid)return max(ask(p<<1,l,r,L,mid),ask(p<<1|1,l,r,mid+1,R));
    if(l<=mid)return ask(p<<1,l,r,L,mid);
    return ask(p<<1|1,l,r,mid+1,R);
}
void solve(){
    n=read();
    rep(i,1,n)a[i]=read();
    build(1,1,1e6);
    ll sm=0;
    rep(i,2,n){
        ll s=max(max(ask(1,1,a[i]-1,1,1e6),ask(1,a[i]+1,1e6,1,1e6)),ask(1,a[i],a[i],1,1e6)+a[i]);
        if(a[i]==a[i-1])tag(1,a[i]);
        change(1,a[i-1],max(sm,s),1,1e6);
        if(a[i]==a[i-1])sm+=a[i];
    }
    cout<<t[1]<<'\n';
}
signed main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    T=read();
    while(T--)solve();
    return 0;
}